package courseDesign;

public class SortCode {
	public static void  main(String []args) {
		int arr[]= {98,4,3,78,2,0,24};
		//quickSort(arr,0,arr.length-1);
		heapSort(arr);
		for(int i: arr)
			System.out.println(i);
	}
	/**交换类排序
	 * 1、冒泡排序 
	 * 2.快速排序 
	 */
	public static void quickSort(int arr[],int l,int r) {
//		int l=0;
//		int r=arr.length-1;
	if(l<r) {
		int p[]=paration(arr,l,r);
		quickSort(arr,l,p[0]-1);
		quickSort(arr,p[1]+1,r);
	}
	}
	public static int [] paration(int arr[],int l,int r){
		/**
		 *  注意  这里的 一些细节点
		 *  arr[r]占用 了 最后一个位置 所以   
		 *  最后 需要把 arr[r]交换到 等于区域 就是  swap(arr,arr[r],);
		 *  more=r   所以 当遇到  比 arr[r]大的 数 时 跟more 前一个数 进行交换  就是 这么 的合理
		 *  表示的  其实 跟 less  是一个 含义 
		 *  less表示的  小于 arr[r]的区域
		 */
		int less=l-1;
		int more=r;
		while(l<more) {
			if(arr[l]<arr[r]) {
				swap(arr,++less,l++);
			}
			// 注意这里 交换 过后 是不用 让l++ 因为交换 来的值 还未  判断
			else if(arr[l]>arr[r]){
				swap(arr,l,--more);
			}
			else {
				l++;
			}
		}
		swap(arr,more,r);
		return new int[] {less+1,more};
	}
//	public static void function() {
//	}
	/**选择类 排序
	 * 1.选择排序 
	 * 2、堆排序
	 * 以 大根堆 为例
	 * 在堆  中 最重要的 两个操作 就是 heapInsert(是 将变量 向上调整   保证整个 堆任然是 大根堆 或者是小根堆)  and
	 *  headpify(是 向下 调正  实现 让整个堆 仍然是 大根堆 或者是小根堆) 的过程
	 *  
	 *  堆  本质 是一个 数组 通过  下标    index而实现 的 一个 完全二叉树  
	 */
	public static void heapSort(int arr[]) {
		if(arr==null || arr.length<2)
			return ;
		for(int i=0;i<arr.length;i++)
			heapInsert(arr,i);
		int size=arr.length;
		swap(arr,0,--size);
//		swap(arr,0,size--);  这样想 是不错的  只是 在 heapify 里面的  while()  判断条件 需要 改变一下  才能 正确
		while(size>0) {
			// 之前好像就出现了 这个问题
			heapify(arr,0,size);
			swap(arr,0,--size);
		}
		
	}
	public static void heapInsert(int arr[],int index) {
		// 注意 这里 是根节点的  时候仍然 是正确的  举例 看一下 就明白了
		while(arr[index]>arr[(index-1)/2]) {
			swap(arr,index,(index-1)/2);
			index=(index-1)/2;
		}
	}
	public static void heapify(int arr[],int index,int heapSize) {
		int left=index*2+1;
		// 如果 下面 这个 条件 不满足 就是说明 index 已经是 最低点 就不用调整
		while(left<heapSize) {
			int largest=left+1<heapSize && arr[left+1]>arr[left] ? left+1 :left;
			largest= arr[largest]>arr[index] ? largest :index; 
			if(largest==index) {
				break;
			}
			swap(arr,index,largest);
			//left=largest*2+1;   这样写 的 话 会出现 一些问题 的  因为 while循环中 是有index参与比较的
			// 不更新 index  的话 必定会出错
			index=largest;
			left=index*2+1;
		}
	}
   /**插入 排序  
    * 1、直接插入排序 （ 规模越小 ， 数据 越有序 速度 越快 ）
    * 所以 希尔排序  就是 从这两个 方面 进行 改进的 的算法
    * 2. shell排序      希  尔排序 
    * 
    *
    */
	
	
	
	
	
	
	public static void swap(int arr[],int i,int j) {
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
	//  注意 这一点 就是 如果 这两个 int 的 变量的 地址是一样的  那就不能 用这种swap
	public static void swapTwoPointZero(int arr[],int i,int j) {
		//  直接 异或运算 的精髓
		arr[i]=arr[i]^arr[j];
		arr[j]=arr[i]^arr[j];
		arr[i]=arr[i]^arr[j];
	}
}
